#include "arvoreB.h"

/* Essa função lê cada caractere do arquivo de registro e coloca na memória */
ptrReg lerRegistro(ptrArq *file,char c,int prr){
  
	int i;
	ptrReg reg = NULL;
	
	reg = malloc(sizeof(struct Registro));
	reg->filha_maior = NULL;
	reg->filha_menor = NULL;
	reg->matricula[0] = c;
	reg->prr = prr;
	for(i = 1;i<9;i++){
		fread(&c,1,1,(*file));
		reg->matricula[i] = c;
	}
	fseek((*file),101,SEEK_CUR);
	return(reg);
}

/* Essa função imprime o registro do arquivo de registros */
void imprimeRegistros(ptrArq *file){
  
	int i;
	char c;
	char matricula[9],nome[101];
	
	for(i = 0;i<9;i++){
		fread(&c,1,1,(*file));
		matricula[i] = c;
	}
	for(i = 0;i<8;i++){
		printf("%c",matricula[i]);
	}
	printf(": ");
	for(i=0;i<101;i++){
		fread(&c,1,1,(*file));
		nome[i] = c;
		printf("%c",nome[i]);
	}
	printf("\n");
}

/* Efetua inicialização da página raiz */
void inicializaPagina(ptrPag *pag_root,ptrPag *pag_atual,ptrReg *reg,int ordem){
  
	int i;
	
	*pag_root = malloc(sizeof(struct Pagina));
	(*pag_root)->pai = NULL;
	(*pag_root)->pagina[0] = *reg;
	for(i=1;i<ordem;i++){
		(*pag_root)->pagina[i] = NULL;
	}
	*pag_atual = *pag_root;
}

/* Insere registro na página */
void insereRegistro(ptrPag *pag_atual,ptrReg *reg,int ordem){
  
	int i;
	
	for(i=0;i<ordem;i++){
		if((*pag_atual)->pagina[i] == NULL){
			(*pag_atual)->pagina[i] = *reg;
			break;
		}
	}
}

/* Verifica se o registro cabe na página atual */
int verificaEspacoInsercaoRegistro(ptrPag *pag_atual,int ordem){
  
	int i;
	
	for(i=0;i < (ordem-1);i++){
		if((*pag_atual)->pagina[i] == NULL){
			return(1);
		}
	}
	return(0);
}

/* Compara as matriculas, retorna 0 se forem iguais, 1 se str1 for menor ou 2 se str2 for menor */
int comparaStrings(char str1[],char str2[]){
  
	int i;
	
	for(i=0;i<8;i++){
		if(str1[i] < str2[i]){
			return(1);
		}
		if(str1[i] > str2[i])
		{
			return(2);
		}
	}
	return(0);
}

/* Ordena os registros nas páginas em modo crescente */
void ordenaRegistros(ptrPag *pag_atual,int ordem){
  
	int i,j = 0,k = 0;
	ptrReg temp = NULL;
	
	while(k < ordem){
		for(i=0;i<ordem;i++) {
			if((*pag_atual)->pagina[i] == NULL){
				j = i;
				while(j < (ordem-1)){
					temp = (*pag_atual)->pagina[j];
					(*pag_atual)->pagina[j] = (*pag_atual)->pagina[j+1];
					(*pag_atual)->pagina[j+1] = temp;
					j++;
				}
			}
		}
		k++;
	}
	i = 0;
	j = 1;
	while((*pag_atual)->pagina[i] != NULL){i++;}
	while(j < i){
		k = 0;
		while(k < (i-1)){
			if(comparaStrings((*pag_atual)->pagina[k]->matricula,(*pag_atual)->pagina[k+1]->matricula) == 2){
				temp = (*pag_atual)->pagina[k];
				(*pag_atual)->pagina[k] = (*pag_atual)->pagina[k+1];
				(*pag_atual)->pagina[k+1] = temp;
			}
			k++;
		}
		j++;
	}
}

/* Ordena os ponteiros dos registros nas páginas */
void ordenaPonteiro(ptrPag *pag_atual,int ordem){
  
	int i;
	
	for(i = 0;i < ordem;i++){
		if(((*pag_atual)->pagina[i] != NULL) && ((*pag_atual)->pagina[i+1] != NULL)){
			(*pag_atual)->pagina[i+1]->filha_menor = (*pag_atual)->pagina[i]->filha_maior;
		}
	}
}

/* Joga o elemento promovido na página pai */
ptrReg utilizaElementoPromovido(ptrPag *pag_atual, int *ind_promov,int ordem){
  
	int i = 0;
	
	while((i < ordem) && ((*pag_atual)->pagina[i] != NULL)){
		i++;
	}
	*ind_promov = i/2;
	return((*pag_atual)->pagina[*ind_promov]);
}

/* Copia uma página para outra */
void copiaPagina(ptrPag *pag_origem,ptrPag *pag_destino,int ordem){
  
	int i;
	
	for(i = 0;i<ordem;i++){
		(*pag_destino)->pagina[i] = (*pag_origem)->pagina[i];
	}
}

/* Limpa a página dos elementos menores que o índice e maior que o índice promovido */
void limpaPagina(ptrPag *pag_menor,ptrPag *pag_maior,int indice,int ordem){
  
	int i;
	
	for(i = ordem;i >= indice;i--){
		(*pag_menor)->pagina[i] = NULL;
	}
	for(i = 0;i <= indice;i++){
		(*pag_maior)->pagina[i] = NULL;
	}
	ordenaRegistros(&(*pag_maior),ordem);
	i=0;
	
	while(((*pag_maior)->pagina[i] != NULL) && ((*pag_maior)->pagina[i]->filha_menor != NULL)){
		(*pag_maior)->pagina[i]->filha_menor->pai = (*pag_maior);
		i++;
	}
	i=0;
	while(((*pag_maior)->pagina[i] != NULL) && ((*pag_maior)->pagina[i]->filha_maior != NULL)){
		(*pag_maior)->pagina[i]->filha_maior->pai = (*pag_maior);
		i++;
	}
}

/* Define como ocorre a promoção de página e como se insere um registro quando a página esta cheia */
void ordenaArvoreB(ptrPag *pag_root,ptrPag *pag_atual,ptrReg *registro,int ordem){
  
	int ind_promov;
	(*pag_atual)->pagina[ordem-1] = *registro;
	ordenaRegistros(&(*pag_atual),ordem);
	ordenaPonteiro(&(*pag_atual),ordem);
	if((*pag_atual)->pai == NULL){
		(*pag_atual)->pai = malloc(sizeof(struct Pagina));
		*pag_root = (*pag_atual)->pai;
	}
	*registro = utilizaElementoPromovido(&(*pag_atual),&ind_promov,ordem);
	(*registro)->filha_maior = malloc(sizeof(struct Pagina));
	(*registro)->filha_menor = *pag_atual;
	(*registro)->filha_maior->pai = (*pag_atual)->pai;
	copiaPagina(&(*registro)->filha_menor,&(*registro)->filha_maior,ordem);
	limpaPagina(&(*registro)->filha_menor,&(*registro)->filha_maior,ind_promov,ordem);
	if(verificaEspacoInsercaoRegistro(&(*pag_atual)->pai,ordem)){
		insereRegistro(&(*pag_atual)->pai,&(*registro),ordem);
		ordenaRegistros(&(*pag_atual)->pai,ordem);
		ordenaPonteiro(&(*pag_atual)->pai,ordem);
	}
	else{
		ordenaArvoreB(&(*pag_root),&(*pag_atual)->pai,&(*registro),ordem);
	}
}

/* Procura a página que abrigará o elemento */
ptrPag insereElementoPagina(ptrPag *pag_atual,char chave[],int ordem){
  
	int i,a;
	
	if(ordem <= 1){printf("Nao existem registros com essa ordem. Saindo do programa.\n");exit(1);}
	if(ordem == 2 ){return(*pag_atual);};
	for(i=0;i < (ordem-2);i++){
		a = comparaStrings(chave,(*pag_atual)->pagina[i]->matricula);
		if(a == 0){
			printf("Essa chave ja existe!\n\n");
			exit(1);
		}else{
			if(a == 1){
				if((*pag_atual)->pagina[i]->filha_menor == NULL){
					return(*pag_atual);
				}else{
					return(insereElementoPagina(&(*pag_atual)->pagina[i]->filha_menor,chave,ordem));
				}
			}else{
				if(((*pag_atual)->pagina[i+1] == NULL) || (comparaStrings(chave,(*pag_atual)->pagina[(i+1)]->matricula) == 1)){
					if((*pag_atual)->pagina[i]->filha_maior == NULL){
						return(*pag_atual);
					}else{
						return(insereElementoPagina(&(*pag_atual)->pagina[i]->filha_maior,chave,ordem));
					}
				}
			}
		}
	}
	if((*pag_atual)->pagina[i]->filha_maior == NULL){
		return(*pag_atual);
	}else{
		return(insereElementoPagina(&(*pag_atual)->pagina[i]->filha_maior,chave,ordem));
	}
}

/* Imprime página no arquivo de índice */
void imprimePaginaArquivoIndice(ptrArq *file_Btree,ptrPag *root,int ordem){
  
	int i,conta_byte = 0;
	
	for(i=0;i<(ordem-1);i++){
		if((*root)->pagina[i] != NULL){
			fwrite(&(*root)->pagina[i]->matricula,9,1,(*file_Btree));
			conta_byte = conta_byte + 9;
			fwrite(&(*root)->pagina[i]->prr,4,1,(*file_Btree));
			conta_byte = conta_byte + 4;
		}else { break;}
	}
	for(i=0;i < (390 - conta_byte);i++){
		fwrite("#",1,1,(*file_Btree));
	}
}

/* Carrega a página atual na memória */
void carregaPagina(ptrArq *file,ptrPag *pagina){
  
	char c;
	int i,j =0;
	
	while(fread(&c,1,1,(*file))!=0){
	  
		if(c == '#'){ break;}/* # = fim da página */
		(*pagina)->pagina[j] = malloc(sizeof(struct Registro));
		(*pagina)->pagina[j]->matricula[0]=c;
		for(i=1;i < 9;i++){
			fread(&(*pagina)->pagina[j]->matricula[i],1,1,(*file));
		}
		fread(&(*pagina)->pagina[j]->prr,4,1,(*file));
		j++;
	}
}

/* Procura chave da página na memória */
int procurarChave(ptrPag *pagina,char matricula[]){
  
	int i=0;
	
	while((*pagina)->pagina[i] != NULL){
		if(comparaStrings((*pagina)->pagina[i]->matricula,matricula) == 0){
			return((*pagina)->pagina[i]->prr);
			break;
		}
		i++;
	}
	return(-1);
}
